package me.chan.sort;

import me.chan.std.StdRandom;

import static me.chan.util.SortUtil.*;

/**
 * Created by JanGin on 2017/9/12.
 */
public class QuickSortWithSentinel {

    private QuickSortWithSentinel() {}

    public static void sort(Comparable[] a) {
        StdRandom.shuffle(a);
        sortWithSentinel(a, 0, a.length - 1);
    }

    private static void sortWithSentinel(Comparable[] a, int lo, int hi) {
        StdRandom.shuffle(a);
        int largest = largest(a);
        exch(a, largest, a.length - 1);
        sort(a, 0, a.length - 1);

    }

    private static int largest(Comparable[] a) {
        assert a != null && a.length > 1;

        int largest = 0;
        for(int i = 1; i < a.length; i++) {
            if(less(a[largest], a[i]))
                largest = i;
        }
        return largest;
    }

    private static void sort(Comparable[] a, int lo, int hi) {
        if (hi <= lo) return;

        int mid = partition(a, lo, hi);
        sort(a, lo, mid - 1);
        sort(a, mid + 1, hi);
    }

    private static int partition(Comparable[] a, int lo, int hi) {
        int i = lo, j = hi;
        Comparable v = a[lo];
        while ( true ) {
            while (less(v, a[--j]));
            while (less(a[++i], v));

            if ( i < j ) {
                exch(a, i, j);
            }
            if (i >= j)
                break;
        }
        exch(a, lo, j);
        return j;
    }

    public static void main(String[] args) {

        Comparable[] arr = {'E', 'E', 'G', 'M', 'R', 'A', 'C', 'E', 'R', 'T'};

        show(arr);

        sort(arr);

        //sortWithSentinel(arr);

        show(arr);
    }
}
